
from math import sqrt
from copy import copy

def enum_prime_util(max_num):
    primes = [2]
    for i in xrange(3, max_num + 1):
        is_prime = True
        for p in primes:
            if p > sqrt(i):
                break
            if i % p == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(i)
    print '%d primes found under %d' % (len(primes), max_num)
    return primes

def factor_util(primes, max_num):
    factors_dict = {}
    for i in xrange(1, max_num + 1):
        factors = []
        j = i
        for p in primes:
            if p > j:
                break
            if j % p == 0:
                factors.append(p)
                while j % p == 0:
                    j /= p
        factors_dict[i] = set(factors)
    print 'all numbers under %d factorized' % (max_num)
    return factors_dict
    
def has_intersec(s0, s1):
    for e in s0:
        if e in s1:
            return True
    return False

def rec_enum(factors_dict, num_primes, start, used_factors):
    for i in xrange(start, 1, -1):
        fi = factors_dict[i]
        if has_intersec(fi, used_factors):
            continue
        else:
            used_factors_rec = used_factors | fi
            if len(used_factors_rec) < num_primes:
                for j in rec_enum(factors_dict, num_primes, i - 1, used_factors_rec):
                    yield i + j
            else:
                yield i

def brute(max_num):
    primes = enum_prime_util(max_num)
    factors_dict = factor_util(primes, max_num)
    max_sum = 0
    for sum in rec_enum(factors_dict, len(primes), max_num, set([])):
        if sum > max_sum:
            print sum
            max_sum = sum

dynamic_dict = {}
dynamic_count = 0
dynamic_dict_hit = 0

def rec_max_dynamic(factors_dict, remain):
    # dynamic_count += 1
    if len(remain) == 0:
        return 0
    elif len(remain) == 1:
        return remain[0]
    max = dynamic_dict.get(remain)
    if max is not None:
        # dynamic_dict_hit += 1
        return max
    max = 0
    for i in remain:
        fi = factors_dict[i]
        new_remain = list(remain)
        for j in remain:
            for fj in factors_dict[j]:
                if fj in fi:
                    new_remain.remove(j)
                    break
        sum = i + rec_max_dynamic(factors_dict, tuple(new_remain))
        if sum > max:
            max = sum
    dynamic_dict[remain] = max
    return max

def brute_dynamic(max_num):
    primes = enum_prime_util(max_num)
    factors_dict = factor_util(primes, max_num)
    print rec_max_dynamic(factors_dict, tuple(range(2, max_num + 1)))
    print 'dynamic dict hit: %d/%d' % (dynamic_dict_hit, dynamic_count)
        
# greedy is not max :(
def greedy(max_num):
    primes = enum_prime_util(max_num)
    from copy import copy
    sum = 0
    cur = 1
    remain = list(reversed(primes))
    while len(remain) > 0:
        for p in copy(remain):
            if cur * p > max_num:
                continue
            else:
                while cur * p < max_num:
                    cur *= p
                remain.remove(p)
        sum += cur
        cur = 1
    return sum

if __name__ == '__main__':
    from sys import argv
    brute_dynamic(int(argv[1]))
    